import java.util.Random;
/**
 * This class represents a linked skip list.
 * @author Matt
 *
 * @param <T>
 */
public class SkipList<T extends Comparable<T>> implements SortedList<T>
{
	private SkipListHead<T> topLeft;
	private SkipListTail<T> topRight;
	private final Random random;
	private int height,size;
	
	public SkipList(Random randomIn)
	{
		this.random = randomIn;
		topLeft = new SkipListHead<T>();
		topRight = new SkipListTail<T>();
		topLeft.setNext(topRight);
		topRight.setPrevious(topLeft);
		height = 1;
		size = 0;
	}
	public SkipList()
	{
		this(new Random());
	}
	/**
	 * Sets the topLeft node to the passed in node
	 * @param node new node
	 */
	public void setTopLeft(SkipListHead<T> node)
	{
		topLeft = node;
	}
	/**
	 * Sets the top right node to the passed in node
	 * @param node new node
	 */
	public void setTopRight(SkipListTail<T> node)
	{
		topRight = node;
	}
	
	public void setSize(int newSize)
	{
		size = newSize;
	}
	/**
	 * sets the height to the passed in int
	 * @param newHeight 
	 */
	public void setHeight(int newHeight)
	{
		height = newHeight;
	}
	/**
	 * Returns the value of height
	 * @return height
	 */
	public int getHeight()
	{
		return height;
	}
	/**
	 * Returns the topLeft node
	 * @return topLeft
	 */
	public SkipListHead<T> getTopLeft()
	{
		return topLeft;
	}
	/**
	 * Returns the top right node
	 * @return topRight
	 */
	public SkipListTail<T> getTopRight()
	{
		return topRight;
	}
	
	
	
	/**
	 * Adds an element to the list.
	 * 
	 * @param element
	 *            The new element
	 */
	public void add(T element)
	{
		SkipListNode<T> newNode = new SkipListNode<T>(element);
		SkipListNode<T> lastPlaced;
		int newHeight = 1;
		SkipListNode<T> probe;
		SkipListNode<T> endProbe = topLeft;
		Boolean increase = random.nextBoolean();
		while(increase == false)
		{
			newHeight++;
			increase = random.nextBoolean();
		}
			
		while(newHeight > height)
		{
			SkipListHead<T> newTopLeft = new SkipListHead<T>();
			SkipListTail<T> newTopRight = new SkipListTail<T>();
			newTopLeft.setNext(newTopRight);
			newTopRight.setPrevious(newTopLeft);
			newTopLeft.setDown(topLeft);
			newTopRight.setDown(topRight);
			topLeft.setUp(newTopLeft);
			topRight.setUp(newTopRight);
			topLeft = newTopLeft;
			topRight = newTopRight;
			height++;	
		}
		int currentLevel = newHeight-1;
		
		int i = height -1;
		
		while(i != currentLevel)
		{
			endProbe  = endProbe.getDown();
			i--;
		}
		
		probe = endProbe;
		while(endProbe != null)
		{
				probe = endProbe;
				Boolean placed = false;
				while(probe.compareTo(newNode) < 0 || !placed)
				{
					if(probe.getNext() instanceof SkipListTail)
					{
						newNode.setNext(probe.getNext());
						newNode.setPrevious(probe);
						probe.getNext().setPrevious(newNode);
						probe.setNext(newNode);		
						placed = true;
					}
					else if(!(probe.getNext() instanceof SkipListTail) && probe.getNext().compareTo(newNode) > 0)
					{
						newNode.setNext(probe.getNext());
						newNode.setPrevious(probe);
						probe.getNext().setPrevious(newNode);
						probe.setNext(newNode);		
						placed = true;
					}
					probe = probe.getNext();		
				}
				lastPlaced = newNode;			
				newNode = new SkipListNode<T>(element);
				if(endProbe.getNext() !=null)
				{
					lastPlaced.setDown(newNode);
					newNode.setUp(lastPlaced);
				}
				endProbe = endProbe.getDown();
		}
		size++;
	}
	
	/**
	 * Removes an element from the list, if it exists.
	 * 
	 * @param element
	 *            The element to remove
	 * @return The element that was removed, or null if the element was not in
	 *         the list
	 */
	public T remove(T element)
	{
	
		Boolean found = false;
		Boolean reachedEnd = false;
		SkipListNode<T> toBeRemoved = new SkipListNode<T>(element);
		SkipListNode<T> endProbe = topLeft;
		SkipListNode<T> probe = endProbe;
		while(endProbe != null && !found)
		{
			while(probe.getNext() != null && !found && !reachedEnd)
			{
				if((probe.getNext() instanceof SkipListTail))
					reachedEnd = true;
				if(probe.equals(toBeRemoved))
				{
					found = true;
					toBeRemoved = probe;
				}
				if(!reachedEnd)
					probe = probe.getNext();
			}
			reachedEnd = false;
			endProbe = endProbe.getDown();
			if(!found)
			probe = endProbe;
		}
		
		while(probe.getDown() != null && found)
		{
			if(probe.getPrevious() instanceof SkipListHead)
			{
				probe.getNext().setPrevious(probe.getPrevious());
			}
			probe.getNext().setPrevious(probe.getPrevious());
			probe.getPrevious().setNext(probe.getNext());
			probe.setUp(null);
			probe = probe.getDown();
		}
		
		if(found)
		{
			size--;
			return probe.getData();
		}
		
		return element;
	}

	/**
	 * Returns, but does not remove, the smallest element in the list.
	 * 
	 * @return The smallest element in the list
	 */
	public T getMin()
	{
		SkipListNode<T> probe = topLeft;
		while(probe.getDown() != null)
			probe = probe.getDown();
		if(probe.getNext() instanceof SkipListTail)
			return null;
		else
			return probe.getNext().getData();
			
	}

	/**
	 * Returns, but does not remove, the largest element in the list.
	 * 
	 * @return The largest element in the list
	 */
	public T getMax()
	{
		SkipListNode<T> probe = topRight;
		while(probe.getDown() != null)
			probe = probe.getDown();
		if(probe.getPrevious() instanceof SkipListHead)
			return null;
		else
			return probe.getPrevious().getData();
	}

	/**
	 * Returns the index of an element in the list.
	 * 
	 * @param element
	 *            The element to look for
	 * @return The index of the element, if it is contained in the list;
	 *         otherwise, (-(insertion point) - 1). The insertion point is
	 *         defined as the point at which the element would be inserted into
	 *         the list
	 */
	public int indexOf(T element)
	{
		Boolean found = false;
		Boolean DNE = false;
		int index = 0;
		SkipListNode<T> target = new SkipListNode<T> (element);
		SkipListNode<T> probe = topLeft;
		while(probe.getDown() != null)
			probe = probe.getDown();
		probe = probe.getNext();
		while(!(probe instanceof SkipListTail) && !found && !DNE)
		{
			if(probe.equals(target))
			{
				found = true;
			}
			else if(probe.getNext().compareTo(target)>0)
				DNE = true;
			probe = probe.getNext();
			
			index++;
		}
		if(found)
			return index;
		else
			return -(index + 1);
	}

	/**
	 * Determines if an element is in the list.
	 * 
	 * @param element
	 *            The element to search for
	 * @return true if the element is in the list, or false otherwise
	 */
	public boolean contains(T element)
	{
		Boolean found = false;
		Boolean endOfList = false;
		SkipListNode<T> toBeFound = new SkipListNode<T>(element);
		SkipListNode<T> endProbe = topLeft;
		SkipListNode<T> probe = endProbe;
		while(endProbe != null && !found)
		{
			while( !found && !endOfList)
			{
				
				if(probe.equals(toBeFound))
				{
					found = true;
				}
				
				else if((probe.getNext() instanceof SkipListTail))
				{
					endOfList = true;
				}
				probe = probe.getNext();
			}
			endOfList = false;
			endProbe = endProbe.getDown();
			probe = endProbe;
		}
		
		return found;
		
	}

	/**
	 * Removes all elements from the list.
	 */
	public void clear()
	{
		topLeft = new SkipListHead<T>();
		topRight = new SkipListTail<T>();
		topLeft.setNext(topRight);
		topRight.setPrevious(topLeft);
		size = 0;
		height = 1;	
	}

	/**
	 * Returns the number of elements in the list.
	 * 
	 * @return The size of the list
	 */
	public int size()
	{
		return size;
	}

	/**
	 * Determines if the list is empty.
	 * 
	 * @return true if the list is empty, or false otherwise
	 */
	public boolean isEmpty()
	{
		return size==0;
	}
}
